package 中等.树;

import util.TreeNode;

/**
 * 最大树 定义：一棵树，并满足：其中每个节点的值都大于其子树中的任何其他值。
 * 给你最大树的根节点 root 和一个整数 val 。
 * 就像 之前的问题 那样，给定的树是利用 Construct(a) 例程从列表 a（root = Construct(a)）递归地构建的：
 * 如果 a 为空，返回 null 。
 * 否则，令 a[i] 作为 a 的最大元素。创建一个值为 a[i] 的根节点 root 。
 * root 的左子树将被构建为 Construct([a[0], a[1], ..., a[i - 1]]) 。
 * root 的右子树将被构建为 Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]]) 。
 * 返回 root 。
 * 请注意，题目没有直接给出 a ，只是给出一个根节点 root = Construct(a) 。
 * 假设 b 是 a 的副本，并在末尾附加值 val。题目数据保证 b 中的值互不相同。
 * 返回 Construct(b) 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-binary-tree-ii
 */
public class 最大二叉树II_998 {

    public static void main(String[] args) {

    }

    /**
     * 注意:
     * root 是一个经过 最大二叉树_654 函数构建好的树
     * val 添加在末尾，那么一定是属于 右节点
     * 思路:
     * 遍历 root 树，如果 val 大于 当前节点的值，那么当前节点是 val节点的左节点，
     * 因为 val 节点是添加在原数组的右侧
     *
     * @param root
     * @param val
     * @return
     */
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        TreeNode curNode = root;
        while (true) {
            if (curNode.val < val) {
                TreeNode leftNode = new TreeNode(curNode.val);
                curNode.val = val;

                leftNode.left = curNode.left;
                leftNode.right = curNode.right;

                curNode.left = leftNode;
                curNode.right = null;
                return root;
            }

            if (curNode.right == null) {
                curNode.right = new TreeNode(val);
                return root;
            }
            curNode = curNode.right;
        }
    }

}
